//https://leetcode.cn/problems/top-k-frequent-elements/
package codeRandomThoughts.Test347前k个高频元素;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //先用map统计元素和其出现的数量
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        //再用一个size为k的小顶堆遍历map,
        //Java的小顶堆为PriorityQueue
        //这里需要自己定义比较器,按照value排序
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (priorityQueue.size() < k) {//如果堆中元素不满k个
                priorityQueue.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > priorityQueue.peek()[1]) {//当前元素比最小值大的时候,把最小值poll掉
                    priorityQueue.poll();//把最小的队头删除
                    priorityQueue.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }

        //依次弹出小顶堆,注意此时和result逆序
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = priorityQueue.poll()[0];
        }
        return result;
    }
}
